/*      > C.Ring - Ring data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "ring.h"

#ifdef test
#include <stdio.h>
#endif

struct link
{
        struct link *next;
        struct link *prev;
        char data[1];
};

typedef struct link *link;

/* Return values from functions */

#define OK      1
#define ERR     0

/* General component routines */

ring ring_new (int obj_len)
{
        register ring r;

        r = malloc(sizeof(struct ring));

        if ( r == NULL )
                return NULL;

        r->top      = NULL;
        r->mark     = NULL;
        r->obj_size = obj_len;

        return r;
}

void ring_free (ring r)
{
        ring_clear(r);
        free(r);
}

void ring_clear (ring r)
{
        link this_entry = r->top;
        link next_entry;
        
        if ( r->top == NULL )
                return;

        do {
                next_entry = this_entry->next;
                free(this_entry);
                this_entry = next_entry;
        } while ( this_entry != (link)r->top );

        r->top = r->mark = NULL;
}

int ring_copy (ring r1, const ring r2)
{
        link from, to;
        link new;
        int size;

        if ( r1->obj_size != r2->obj_size )
                return ERR;

        ring_clear(r1);

        size = r2->obj_size;
        from = r2->top;

        if ( from == NULL )
                return ERR;
        else
        {
                new = malloc(sizeof(struct link) - 1 + size);
                if ( new == NULL )
                        return ERR;

                memcpy(new->data,from->data,size);
                new->next = NULL;
                new->prev = NULL;

                to = new;
                r1->top = new;

                if ( from == (link)r2->mark )
                        r1->mark = to;

                from = from->next;

                while ( from != (link)r2->top )
                {
                        new = malloc(sizeof(struct link) - 1 + size);
                        if ( new == NULL )
                        {
                                ring_clear(r1);
                                return ERR;
                        }

                        memcpy(new->data,from->data,size);
                        new->next = NULL;
                        new->prev = to;

                        to->next = new;
                        to = to->next;

                        if ( from == (link)r2->mark )
                                r1->mark = to;

                        from = from->next;
                }

                ((link)r1->top)->prev = to;
                to->next = r1->top;
        }

        return OK;
}

int ring_equal (const ring r1, const ring r2)
{
        link p1 = r1->top;
        link p2 = r2->top;
        int size;

        if ( r1->obj_size != r2->obj_size )
                return 0;

        size = r1->obj_size;
        if ( p1 == NULL || p2 == NULL )
                return ( p1 == p2 );
        else if ( memcmp(p1->data,p2->data,size) != 0 )
                return 0;
        else if ( p1 == (link)r1->mark && p2 != (link)r2->mark )
                return 0;
        else
        {
                p1 = p1->next;
                p2 = p2->next;

                while ( p1 != (link)r1->top )
                {
                        if ( p2 == (link)r2->top )
                                return 0;
                        else if ( memcmp(p1->data,p2->data,size) != 0 )
                                return 0;
                        else if
                        (
                                p1 == (link)r1->mark
                        &&
                                p2 != (link)r2->mark
                        )
                                return 0;
                        else
                        {
                                p1 = p1->next;
                                p2 = p2->next;
                        }
                }

                return ( p2 == (link)r2->top );
        }
}

int ring_empty (const ring r)
{
        return ( r->top == NULL );
}

int ring_size (const ring r)
{
        int i = 0;
        link p;

        if ( r->top == NULL )
                return 0;

        p = r->top;

        do {
                ++i;
                p = p->next;
        } while ( p != (link)r->top );

        return i;
}

int ring_iterate (const ring r, int (*process)(void *, int))
{
        int ret;
        link p;
        int at_mark;

        if ( r->top == NULL )
                return 1;

        p = r->top;

        do {
                at_mark = ( p == r->mark );

                ret = (*process)(p->data,at_mark);

                /* Non-zero => stop processing here */

                if ( ret != 0 )
                        break;

                p = p->next;

        } while ( p != (link)r->top );

        /* Negative => Abnormal (error) termination */

        return ( ret >= 0 );
}

/* Ring-specific routines */

int ring_insert (ring r, const void *object)
{
        link new;
        link p = r->top;

        new = malloc(sizeof(struct link) - 1 + r->obj_size);

        if ( new == NULL )
                return ERR;

        memcpy(new->data,object,r->obj_size);

        if ( p == NULL )
        {
                new->next = new;
                new->prev = new;
                r->mark = new;
        }
        else
        {
                new->next = p;
                new->prev = p->prev;
                new->next->prev = new;
                new->prev->next = new;
        }

        r->top = new;

        return OK;
}

int ring_pop (ring r)
{
        link p = r->top;

        if ( p == NULL )
                return ERR;

        else if ( p->next == p )
        {
                free(p);
                r->top = NULL;
                r->mark = NULL;
        }

        else
        {
                p->prev->next = p->next;
                p->next->prev = p->prev;
                if ( p == (link)r->mark )
                        r->mark = p->next;
                r->top = p->next;
                free(p);
        }

        return OK;
}

int ring_rotate (ring r, int dir, int n)
{
        link p = r->top;
        int fwd = ( dir == Forward );

        if ( n < 0 )
        {
                fwd = !fwd;
                n = -n;
        }

        if ( p == NULL )
                return ERR;

        if ( fwd )
        {
                while ( n-- > 0 )
                        p = p->next;
        }
        else
        {
                while ( n-- > 0 )
                        p = p->prev;
        }
        
        r->top = p;

        return OK;
}

void *ring_top (const ring r)
{
        if ( r->top == NULL )
                return NULL;

        return ((link)r->top)->data;
}

void ring_mark (ring r)
{
        r->mark = r->top;
}

void ring_tomark (ring r)
{
        r->top = r->mark;
}

int ring_atmark (const ring r)
{
        return ( r->top == r->mark );
}

/*---------------------------------------------------------------------------*/

#ifdef test

int print (void *ptr, int at_mark)
{
        printf("%d%s", *(int *)ptr, (at_mark ? "* " : " ") );
        return STATUS_CONTINUE;
}

void ring_dump (ring r)
{
        printf("Ring: ");
        ring_iterate(r,print);
        putchar('\n');
}
#endif

/*---------------------------------------------------------------------------*/

#ifdef test

#define BUFLEN 255

int main (void)
{
        char buf[BUFLEN], str[BUFLEN];
        int i, j, num;
        ring r[10];

        for ( i = 0; i < 10; ++i )
                r[i] = ring_new(sizeof(int));

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                if ( buf[0] == '\n' || buf[0] == '\0' )
                        continue;
                else if ( sscanf(buf,"clear %1d",&i) == 1 )
                        ring_clear(r[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        ring_copy(r[i],r[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(ring_equal(r[i],r[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(ring_empty(r[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",ring_size(r[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        ring_dump(r[i]);
                else if ( sscanf(buf,"insert %1d %d",&i,&num) == 2 )
                        ring_insert(r[i],&num);
                else if ( sscanf(buf,"pop %1d",&i) == 1 )
                {
                        if ( !ring_pop(r[i]) )
                                printf("Empty\n");
                }
                else if ( sscanf(buf,"rotate %1d %s %d",&i,str,&num) == 3 )
                        ring_rotate(r[i],(str[0]=='f'),num);
                else if ( sscanf(buf,"top %1d",&i) == 1 )
                {
                        int *p = ring_top(r[i]);
                        if ( p == NULL )
                                printf("Empty\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( sscanf(buf,"mark %1d",&i) == 1 )
                        ring_mark(r[i]);
                else if ( sscanf(buf,"to mark %1d",&i) == 1 )
                        ring_tomark(r[i]);
                else if ( sscanf(buf,"at mark %1d",&i) == 1 )
                        printf("%s\n",(ring_atmark(r[i]) ? "yes" : "no"));
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        printf("Deleting r[0-9]\n");
        for ( i = 0; i < 10; ++i )
                ring_free(r[i]);

        return 0;
}

#endif
